"""
https://leetcode.cn/problems/count-integers-with-even-digit-sum/
"""

import random
from functools import cache


class Solution:
    def countEven(self, num: int) -> int:
        res = 0
        for i in range(1, num + 1):
            temp = i
            digit_sum = 0
            while temp:
                digit_sum += temp % 10
                temp //= 10
            if digit_sum % 2 == 0:
                res += 1
        return res

    # i: 当前要搞第几位
    # free: 之前的决策是如何的
    #       True: 之前没有选择过数字 或 之前选了数字但是小于那个限制。     那么从这里开始，我可以随意选择数字
    #       False: 之前选了数字但是==那个限制。      从这里开始每一步都得至少 <=
    def countEven2(self, num: int) -> int:
        num = str(num)
        n = len(num)

        @cache
        def f(i, even, free):
            if i == n:
                return 1 if even else 0  # 之前至少的选过数字
            res = 0
            if free:  # 这里随意选择
                res += 5 * f(i + 1, True, True)
                res += 5 * f(i + 1, False, True)
            else:  # 这里不能选择超过 num[i] 的
                cur = int(num[i])
                for digit in range(cur):
                    is_even = (even and (digit & 1 == 0)) or (
                        not even and (digit & 1 == 1)
                    )
                    res += f(i + 1, is_even, True)
                is_even = (even and (cur & 1 == 0)) or (not even and (cur & 1 == 1))
                res += f(i + 1, is_even, False)
            return res

        # 删除0
        return f(0, True, False) - 1


for _ in range(100):
    num = random.randint(1, 100)
    print(Solution().countEven(num))
    print(Solution().countEven2(num))
